This invention relates to machine vision, a particularly to machine vision methods and apparatuses for searching for instances of an image of a pattern or shape within an image.
One known way to find the pose of an instance of a particular shape within an image is to create a model of the shape, and then break the model of the shape up into parts called xe2x80x9csub-modelsxe2x80x9d, and then find the poses of each of the sub-models in the image, and fit the found poses of each sub-model to the model of the original shape. A particular example of a tool that uses such a strategy is the sub-model search tool, described in the co-pending patent application entitled xe2x80x9cA Method and Apparatus for Modeling and Inspecting Objects Using Machine Visionxe2x80x9d, U.S. patent application Ser. No. 09/054,968, filed Apr. 3, 1998, herein incorporated by reference. This invention automatically breaks up a geometric model into sub-models, roughly finds the entire model within the image, refines the positions of the sub-models within local image neighborhoods, and fits the refined locations of the sub-models to their positions within the model so as to refine the pose of the model.
This sub-model methodology has an advantage of being more tolerant to certain types of deformations between the model and the instance of the model in the image. A major drawback, however, is that substantial errors in the found sub-model poses are therefore possible when sub-models are incorrectly found by the underlying vision tools, or when there is confusing clutter in the image.
The invention provides a method for finding a pose of a geometric model of an object within an image of a scene containing the object that includes providing sub-models of the geometric model; and providing found poses of the sub-models in the image. The method can also include selecting sub-models of the geometric model based on pre-it selection criteria and/or post-fit selection criteria so as to provide selected sub-models of the geometric model. The invention also provides methods for ensuring that the new fit conforms to user-specified requirements, such as requiring that skew or aspect components of the final model pose be below some user-specified threshold. In the case that these conditions are not met, the entire validation process is performed with the new estimate of model pose.
This retry strategy is itself performed as many times as necessary to either produce a model pose that conforms to user requirements, or until an insufficient number of sub-model poses remain. Therefore, the invention not only allows sub-model outliers to be discarded so as to obtain a more accurate model pose, but also reduces the possibility of xe2x80x9cfalse positivesxe2x80x9d, i.e., returning a model pose when the model does not exist within the image.
The invention automatically removes, disqualifies, or disables found sub-model poses when they fail to satisfy certain user-specified requirements. Examples of such requirements include thresholds on deviations between the found sub-model poses and their corresponding expected poses based on the final model pose, as well as limits on the sub-model statistics (e.g., measurements of the quality of fit between the sub-model and the image at the found pose). The remaining, validated sub-models can then be used to re-compute a (presumably) more accurate fit.
The present invention can serve as a xe2x80x9cback endxe2x80x9d to a sub-model based shape finder, such as the one disclosed in xe2x80x9cObject Image Search Using Sub-modelsxe2x80x9d, U.S. patent application Ser. No. 09/054,968, filed Apr. 3, 1998.
In one general aspect, the invention provides a method for finding a pose of a geometric model of an object within an image of a scene containing the object, wherein the method includes providing sub-models of the geometric model; providing found poses of the sub-models in the image; selecting sub-models of the geometric model based on pre-fit selection criteria to provide selected sub-models of the geometric model; and fitting the selected sub-models of the geometric model to respective found poses of the sub-models in the image, so as to provide a pose of the geometric model in the image.
In a preferred embodiment, sub-model statistics are also provided. In a further preferred embodiment, the pre-fit selection criteria includes criteria based on the sub-model statistics. It is also sometimes advantageous for the pre-fit selection criteria to include criteria based on the sub-model poses.
In some embodiments, an initial pose is provided of the geometric model in the image.
In other embodiments, the pre-fit selection criteria include criteria based on a deviation of the found poses of the sub-models from expected poses of the sub-models, the expected poses being computed using the sub-models of the geometric model and the initial pose of the geometric model in the image.
In preferred embodiments, the sub-model statistics include measurements of the quality of fit between each sub-model and the image at the found pose of that sub-model.
In some embodiments, providing the found poses of the sub-models includes using a sub-model-based location method.
The method can also include checking the pose of the geometric model in the image using pose quality criteria, and discarding the pose if it does not satisfy the pose quality criteria.
In another general aspect of the method of the invention, the method includes providing initial sub-models of the geometric model; providing found poses of the sub-models in the image; fitting the initial sub-models of the geometric model to respective found poses of the sub-models in the image, so as to provide an intermediate pose of the geometric model in the image; selecting sub-models based on post-fit selection criteria to provide selected sub-models; and only if selecting sub-models based on post-fit selection criteria does not select all of the initial sub-models, fitting the selected sub-models of the geometric model to respective found poses of the sub-models in the image, so as to provide a refined pose of the geometric model in the image. In a preferred embodiment, this general aspect of the method further includes providing sub-model statistics. In a preferred embodiment, the sub-model statistics include measurements of the quality of fit between each sub-model and the image at the found pose of that sub-model.
In another preferred embodiment, this general aspect of the method can also include providing an initial pose of the geometric model in the image.
In preferred embodiments the post-fit selection criteria includes criteria based on the sub-model statistics and/or sub-model poses. Also, the post-fit selection criteria can include criteria based on a deviation of the found poses of the sub-models from expected poses of the sub-models, the expected poses being computed using the sub-models of the geometric model and the initial pose of the geometric model in the image. Further, the post-fit selection criteria can include criteria based on a deviation of the found poses of the sub-models from expected poses of the sub-models, the expected poses being computed using the sub-models of the geometric model and the intermediate pose of the geometric model in the image.
In preferred embodiments, providing the found poses of the sub-models includes using a sub-model-based location method.
In further preferred embodiments, the method also includes checking one of the intermediate pose of the geometric model and the refined pose of the geometric model in the image using pose quality criteria, and discarding the pose if it does not satisfy the pose quality criteria, and then returning to selecting sub-models.
In another general aspect of the invention, a method is provided for finding the pose of a geometric model of an object within an image of a scene containing the object, wherein the method includes providing sub-models of the geometric model; providing found poses of the sub-models in the image; selecting sub-models based on pre-fit selection criteria to provide pre-fit selected sub-models; fitting the pre-fit selected sub-models of the geometric model to respective found poses of the sub-models in the image, so as to provide an intermediate pose of the geometric model in the image; selecting sub-models based on post-fit selection criteria to provide post-fit selected sub-models; and, only if selecting sub-models based on post-fit selection criteria does not select all of the sub-models, returning to selecting sub-models based on pre-fit selection criteria. In a preferred embodiment, this aspect of the method further includes checking one of the intermediate pose of the geometric model and the refined pose of the geometric model in the image using pose quality criteria, and discarding the pose if it does not satisfy the pose quality criteria, and then returning to selecting sub-models based on pre-it selection criteria.